package com.javabasic.algorithm.leetcode;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/7/4 23:58
 * @Version 1.0
 **/
public class RemoveDuplicatesFromSortedList {

    /**
     * 解法一：逻辑解法，直接把链表当成数组一样来处理就可以了
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        int pre = head.val;
        ListNode resultHead = new ListNode(pre);
        ListNode restltTag = resultHead;
        while (head.next != null) {
            head = head.next;
            if (pre != head.val) {
                pre = head.val;
                restltTag.next = new ListNode(pre);
                restltTag = restltTag.next;
            }
        }
        return resultHead;
    }

    /**
     * 解法二：递归解法
     * @param head
     * @return
     */
    public ListNode deleteDuplicates2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        head.next = deleteDuplicates2(head.next);
        // 如果后一个节点值，和当前节点值相等将引用后移，不能将当前指针的next指为null,因为head.next之后的数据会因此丢失
        if (head.val == head.next.val) {
            head = head.next;
        }
        return head;
    }
}
